Three-dimensional computer models of a real-world environment are useful in a wide variety of applications. For example, such models can be used in applications such as immersive gaming, augmented reality, architecture/planning, robotics, and engineering prototyping.
Depth cameras (also known as z-cameras) can generate real-time depth maps of a real-world environment. Each pixel in these depth maps corresponds to a discrete distance measurement captured by the camera from a 3D point in the environment. This means that these cameras provide depth maps which are composed of an unordered set of points (known as a point cloud) at real-time rates.
However, generating a useful 3D model of the environment using the depth maps provided by a depth camera is complex. With many depth cameras, each individual depth map is of too low resolution and has too high noise to generate a sufficiently accurate and detailed 3D model. Furthermore, many applications utilize a surface reconstruction of the sensed environment rather than point clouds. For example, a 3D reconstructed surface model can be used in a physics simulation to model the effect of physical interactions between virtual objects and real objects sensed in the environment by the depth camera. A point cloud does not work well in this scenario because there are holes throughout the model, due to the lack of connectivity between the individual points in the point cloud.
To infer surface geometry by combining multiple frames of point clouds from the depth camera into a coherent, usable model and determining the connectivity between points in these point clouds is computationally very intensive. Surface reconstruction is the process of extracting the surfaces visible to the camera by inferring this connectivity. Given the amount of data being received in real-time from the depth camera and the desire to support interactive rates, known algorithms such as Poisson surface reconstruction are too computationally expensive to support real-time processing.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known 3D reconstruction techniques.